package Algorithm.interview;

/**
 * @Author self
 * @Date 2024/10/17 21:59
 * @Describe 求一串数据流的中位数
 *
 * 该Java函数实现了一个中位数查找器 MedianFinder，通过维护两个优先队列（最大堆和最小堆）来动态计算中位数：
 * 构造方法：初始化两个堆，maxHeap 存储较小的一半数据，minHeap 存储较大的一半数据。
 * addNum 方法：
 * 将新数加入 maxHeap。
 * 将 maxHeap 的最大值移至 minHeap。
 * 如果 maxHeap 的大小小于 minHeap，则将 minHeap 的最小值移回 maxHeap，以保持平衡。
 * findMedian 方法：
 * 如果 maxHeap 的大小大于 minHeap，返回 maxHeap 的最大值。
 * 否则，返回两个堆顶端元素的平均值。
 */
import java.util.PriorityQueue;

public class MedianFinder {
    private PriorityQueue<Integer> maxHeap; // 最大堆，用于存储较小的一半
    private PriorityQueue<Integer> minHeap; // 最小堆，用于存储较大的一半

    public MedianFinder() {
        maxHeap = new PriorityQueue<>((a, b) -> b - a); // 最大堆
        minHeap = new PriorityQueue<>(); // 最小堆
    }

    public void addNum(int num) {
        maxHeap.offer(num); // 将新数加入最大堆
        minHeap.offer(maxHeap.poll()); // 将最大堆的最大值移到最小堆
        // 平衡两个堆
        if (maxHeap.size() < minHeap.size()) {
            maxHeap.offer(minHeap.poll());
        }
    }

    public double findMedian() {
        if (maxHeap.size() > minHeap.size()) {
            return maxHeap.peek(); // 最大堆的最大值
        } else {
            return (maxHeap.peek() + minHeap.peek()) / 2.0; // 两个堆的顶端元素平均
        }
    }

    public static void main(String[] args) {
        MedianFinder medianFinder = new MedianFinder();
        medianFinder.addNum(1);
        medianFinder.addNum(2);
        System.out.println(medianFinder.findMedian()); // 输出 1.5
        medianFinder.addNum(3);
        System.out.println(medianFinder.findMedian()); // 输出 2.0
    }
}

